package A一周刷爆LeetCode.A基础班.C认识NlogN的排序;

import A一周刷爆LeetCode.A基础班.B认识复杂度和简单排序算法.Sort;

import java.util.Objects;

/**
 * @author wei.zhao
 * @description: 堆排序
 * @date 2022年01月18日 16:11
 */
public class Code09_HeapSort extends Sort {

    @Override
    public void sort(int[] arr) {
        if (Objects.isNull(arr) || arr.length < 2) {
            return;
        }
        // 将数组变成大根堆
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr, i);
        }
        int heapIndex = arr.length - 1;
        while (heapIndex > 0) {
            //第一位与最后一位交换
            swap(arr, 0, heapIndex--);
            //堆化
            heapify(arr, heapIndex);
        }
    }

    // 将i索引位数据堆化
    private void heapInsert(int[] arr, int i) {
        while (arr[i] > arr[(i - 1) / 2]) {
            swap(arr, i, (i - 1) / 2);
            i = (i - 1) / 2;
        }
    }

    // 堆化，相比较heapify2将循环条件做了拆分，在里面加了个break，防止条件过长。
    private void heapify(int[] arr, int heapIndex) {
        int i = 0;
        int l = 2 * i + 1;
        while (l <= heapIndex) {
            int r = l + 1;
            // 最大的子节点索引位
            int largestIndex = r > heapIndex ? l : arr[l] > arr[r] ? l : r;
            if (arr[largestIndex] > arr[i]) {
                swap(arr, i, largestIndex);
                i = largestIndex;
                l=2*i+1;
            } else {
                break;
            }
        }
    }

    // 堆化
    private void heapify2(int[] arr, int heapIndex) {
        int temp = 0;
        while (arr[temp] < Math.max(2 * temp + 1 > heapIndex ? Integer.MIN_VALUE : arr[2 * temp + 1], 2 * temp + 2 > heapIndex ? Integer.MIN_VALUE : arr[2 * temp + 2])) {
            int maxIndex = (2 * temp + 1 > heapIndex ? Integer.MIN_VALUE : arr[2 * temp + 1]) > (2 * temp + 2 > heapIndex ? Integer.MIN_VALUE : arr[2 * temp + 2]) ? 2 * temp + 1 : 2 * temp + 2;
            swap(arr, temp, maxIndex);
            temp = maxIndex;
        }
    }

}
